import ShpConverterTopology from './index.js'

function initHashChains(xx, yy) {
  // Performance doesn't improve much above ~1.3 * point count
  const n = xx.length
  const m = Math.floor(n * 1.3) || 1
  const hash = ShpConverterTopology.getXYHash(m)
  const hashTable = new Int32Array(m)
  const chainIds = new Int32Array(n) // Array to be filled with chain data
  let key = null
  let j = null 

  for (let i=0; i<n; i++) {
    let x = xx[i]
    let y = yy[i]
    if (x != x || y != y) {
      j = -1 // NaN coord: no hash entry, one-link chain
    } else {
      key = hash(x, y)
      j = hashTable[key] - 1 // coord ids are 1-based in hash table; 0 used as null value.
      hashTable[key] = i + 1
    }
    chainIds[i] = j >= 0 ? j : i // first item in a chain points to self
  }
  return chainIds
}

function initPointChains(xx, yy) {
  const chainIds = initHashChains(xx, yy)
  let j = null
  let prevMatchId = null
  let prevUnmatchId = null

  // disentangle, reverse and close the chains created by initHashChains()
  for (let i = xx.length-1; i>=0; i--) {
    let next = chainIds[i]
    if (next >= i) continue
    prevMatchId = i
    prevUnmatchId = -1
    do {
      j = next
      next = chainIds[j]
      if (yy[j] == yy[i] && xx[j] == xx[i]) {
        chainIds[j] = prevMatchId;
        prevMatchId = j;
      } else {
        if (prevUnmatchId > -1) {
          chainIds[prevUnmatchId] = j;
        }
        prevUnmatchId = j;
      }
    } while (next < j);
    if (prevUnmatchId > -1) {
      // Make sure last unmatched entry is terminated
      chainIds[prevUnmatchId] = prevUnmatchId;
    }
    chainIds[i] = prevMatchId; // close the chain
  }
  return chainIds;
}
export default {
  initPointChains,
}
